#include <stdio.h>
#include "genlib.h"
#include "simpio.h"
#include "strlib.h"
#include "benchmark.h"
#include "bucket_sort.h"
#include "insertion_sort.h"
#include "merge_sort.h"
#include "quick_sort.h"
#include "selection_sort.h"
#include "utils.h"

/* Constants */
#define MAX_RECORDS 50000000
#define MIN_RECORDS 1
#define NUM_ALGORITHMS 5
#define NUM_INTERVALS 1
#define BENCHMARK_RUNS 100

/* Prototypes */
static algorithmT setAlgorithm(void);
static int setNumRecords(void);
static int setArrayType(void);
static char* getAlgorithmName(algorithmT algorithm);
static int* generateArray(int numRecords, int arrayType);
static void printArray(int a[], int numRecords, bool before);
static void executeAlgorithm(int algorithm, int a[], int numRecords);


int main() {
	int i, numRecords, arrayType, *myArray;
	algorithmT algorithm;
	benchmark = New(benchmarkT);

	Randomize();

	// Main loop:
	while (TRUE) {
		// Get user input:
		algorithm = setAlgorithm();
		arrayType = setArrayType();
		numRecords = setNumRecords();

		myArray = generateArray(numRecords, arrayType);

		// Print the generated array:
		if (numRecords <= 1000)
			printArray(myArray, numRecords, TRUE);
	
		// Execute the given algorithm & benchmark it:
		benchmarkStart(getAlgorithmName(algorithm), benchmark);
		for (i=0; i<BENCHMARK_RUNS; i++) {
			executeAlgorithm(algorithm, myArray, numRecords);
			if (i != BENCHMARK_RUNS-1) {
				myArray = generateArray(numRecords, arrayType);
			}
		}
		benchmarkEnd(benchmark);

		// Average values:
		benchmark->numCritOp = benchmark->numCritOp/BENCHMARK_RUNS;
		benchmark->elapsed = benchmark->elapsed/BENCHMARK_RUNS;

		// Print the sorted array:
		if (numRecords <= 1000)
			printArray(myArray, numRecords, FALSE);
			
		// Save the data to a text file:
		saveBenchToFile(algorithm, numRecords, arrayType, benchmark->numCritOp, benchmark->elapsed);
			
		// Print data:
		printBenchmark();
		printf("---\n");
		printf("NOTE: %d runs where done with different arrays. Values above is the averages.\n\n", BENCHMARK_RUNS);
			
		// Free memory resources:
		//free(myArray);
		//FreeBlock(myArray);
	
		system("pause");
		system("cls");
	}
}

static algorithmT setAlgorithm() {
	int algorithm = -1;
	printf("\nSorting algorithm:\n");
	printf(" 1. Selection sort\n");
	printf(" 2. Quick sort\n");
	printf(" 3. Insertion sort\n");
	printf(" 4. Merge sort\n");
	printf(" 5. Bucket sort\n");
	while (algorithm < SELECTION_SORT || algorithm > BUCKET_SORT) {
		printf("\nYour choice: ");
		algorithm = GetInteger();
		algorithm--;
	}
	return (algorithmT) algorithm;
}

static int setNumRecords() {
	int numRecords = -1;
	printf("\nNumber of records:\n");
	while (numRecords < MIN_RECORDS || numRecords > MAX_RECORDS) {
		printf("Your choice: ");
		numRecords = GetInteger();
	}
	return numRecords;
}

static int setArrayType() {
	int arrayType = -1;
	printf("\nArray type:\n");
	printf(" 1. Randomized\n");
	printf(" 2. Reversed\n");
	printf(" 3. Almost sorted\n");
	printf(" 4. Sorted\n");
	while (arrayType < RANDOM_ARRAY || arrayType > SORTED_ARRAY) {
		printf("Your choice: ");
		arrayType = GetInteger();
		arrayType--;
	}
	return arrayType;
}

static char* getAlgorithmName(algorithmT algorithm) {
	string aName = "INVALID ALGORITHM";
	switch (algorithm) {
		case SELECTION_SORT:	aName = "Selecion sort";	break;
		case QUICK_SORT:		aName = "Quick sort";		break;
		case INSERTION_SORT:	aName = "Insertion sort";	break;
		case MERGE_SORT:		aName = "Merge sort";		break;
		case BUCKET_SORT:		aName = "Bucket sort";		break;
	}
	return aName;
}

static int *generateArray(int n, int arrayType) {
	int i, k, x, y, *a, j=1;
	a = NewArray(n, int);

	switch (arrayType) {
		case RANDOM_ARRAY:
			for (i=0; i<n; i++) {
				a[i] = RandomInteger(1, n);
			}
		break;
		case REVERSED_ARRAY:
			for (i=n-1; i>=0; i--) {
				a[i] = j;
				j++;
			}
			break;
		case ALMOST_SORTED_ARRAY:
			for (i=0; i<n; i++) {
				a[i]=i+1;
			}
			for (j=0; j<(n/40); j++) {
				x = RandomInteger(0, n-1);
				y = RandomInteger(0, n-1);
				swap(a, x, y);
			}
			break;
		case SORTED_ARRAY:
			for (i=0; i<n; i++) {
				a[i] = i+1;
			}
			//swap(a, 0, n-1);
			break;
	}
	return a;	
}

static void printArray(int a[], int n, bool before) {
	int i;
	printf("\n\n--- %s array sorting ---\n", before ? "Before" : "After");
	for (i=0; i<n; i++)
		printf("#%d : %d\n", i, a[i]);
}

static void executeAlgorithm(int algorithm, int a[], int n) {
	int i, high = 0;
	switch(algorithm) {
		case SELECTION_SORT:	selectionSort(a, n);				break;
		case QUICK_SORT:		quickSort(a, 0, n-1);			break;
		case INSERTION_SORT:	insertionSort(a, n);				break;
		case MERGE_SORT:		mergeSort(a, n);					break;
		case BUCKET_SORT:
			for (i=0; i<n; i++) if (a[i] > high) high = a[i];
			bucketSort(a, n, high);									break;
		default:					Error("INVALID ALGORITHM");	break;
	}
}